package swardToOffer.method_3_backtracking;

/**
 * @Author ChanZany
 * @Date 2021/5/20 16:20
 * @Version 1.0
 */
// 面试题12：矩阵中的路径
// 题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有
// 字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、
// 上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入
// 该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字
// 母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个
// 字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
// A B T G
// C F C S
// J D E H
public class StringPathInMatrix {
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    boolean flag;
    public boolean isExist(char[][] a, String input) {
        if (input == null) return false;
        boolean[][] visit = new boolean[a.length][a[0].length];
        int x=0,y=0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++) {
                if (input.charAt(0)==a[i][j]){
                    x = i;
                    y = j;
                }
            }
        }
        isExist(a,input,x,y,visit);
        return flag;
    }
    public void isExist(char[][] a, String input, int x, int y, boolean[][] visit) {
        //假设以及找到了矩阵中起点的位置x,y并传入
        if (input.equals("")) {
            flag = true;
            return;
        }
        if (a[x][y]==input.charAt(0)){
            //回溯法
            for (int i = 0; i < 4; i++) {
                if (x + dx[i] <= a.length -1 && x + dx[i] >= 0 &&
                    y + dy[i] <= a[0].length - 1 && y + dy[i]>=0 && !visit[x + dx[i]][y + dy[i]]) {
                    visit[x + dx[i]][y + dy[i]] = true;
                    isExist(a, input.substring(1), x + dx[i], y + dy[i], visit);
                    visit[x + dx[i]][y + dy[i]] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        StringPathInMatrix Main = new StringPathInMatrix();
        char[][] chars = new char[3][4];
        chars[0] = new char[]{'A','B','T','G'};
        chars[1] = new char[]{'C','F','C','S'};
        chars[2] = new char[]{'J','D','E','H'};
        System.out.println(Main.isExist(chars, "CFCS"));
        System.out.println(Main.isExist(chars, null));
        char[][] chars2 = new char[1][4];
        chars2[0] = new char[]{'A','B','T','G'};
        System.out.println(Main.isExist(chars2, "ABT"));
    }
}
